<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        function Node(val) {
            this.val = val;
            this.left = null;
            this.right = null;
        }
        var a = new Node(4)
        var b = new Node(2)
        var c = new Node(7)
        var d = new Node(1)
        var e = new Node(3)
        var f = new Node(6)
        var g = new Node(9)
        a.left = b
        a.right = c
        b.left = d
        b.right = e
        c.left = f
        c.right = g

        /* 
        1 时间 O(N) 最坏情况，一层一个，第一个while执行n次
          空间 O(N) quene存储节点
        */
        function reverNode (root, left, right) {
            let temp = left
            left = right
            right = temp
            root.left = left
            root.right = right
        }
        var invertTree = function (root) {
            if (!root) return root
            let queue = []
            queue.push(root)
            while (queue.length > 0) {
                let len = queue.length
                while (len--) {
                    let node = queue.shift()
                    reverNode(node, node.left, node.right)
                    node.left && queue.push(node.left)
                    node.right && queue.push(node.right)
                }
            }
            return root
        };
        console.log(invertTree(a));
    </script>
</body>

</html>